package com.example.leetcode.trainingcamp.week3.Sunday;

import java.util.Stack;

/** 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 */
public class Test42 {

    public int trap(int[] height) {
        int len = height.length;
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i =0 ;i<len;i++){
            while (!stack.isEmpty() && height[i] > height[stack.peek()]){
                // 要是能围住水，必须需要三个元素，并且中间那个高度低于左右两边
                Integer pop = stack.pop();
                if (stack.isEmpty()){
                    // 说明栈就1个元素
                    break;
                }
                Integer peek = stack.peek();
                int minHeight = Math.min(height[i],height[peek]) - height[pop];
                int distance = i - peek -1;
                sum = sum + (distance) * minHeight;
            }
            stack.push(i);
        }
        return sum;
    }
}


class Demo42{
  public static void main(String[] args) {
    int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
    Test42 t = new Test42();
    System.out.println(t.trap(height));
  }
}